#include <stdio.h>
#include <string.h>
#include <cstdlib>
typedef int ElementType; // 元素类型 (typedef作用是起别名)
//链表
typedef struct Node {
    ElementType data; // 数据域
    struct Node* next; // 指针域
} Node;

Node* InitList() { // 初始化链表(返回指针的函数,语法不懂可看菜鸟教程)
    Node* head = (Node*)malloc(sizeof(Node)); // 分配头结点内存
    head->data = 0; // 头结点数据域置0
    head->next = NULL; // 头结点指针域置空
    return head; // 返回头结点指针
}

int inserHead(Node* head, ElementType e) { // 头插法插入元素
    Node* newNode = (Node*)malloc(sizeof(Node)); // 分配新节点内存
    if (!newNode) { // 内存分配失败
        printf("内存分配失败，无法插入元素\n");
        return 0; // 插入失败
    }
    newNode->data = e; // 设置新节点数据域
    newNode->next = head->next; // 新节点指针域指向当前第一个节点
    head->next = newNode; // 头结点指针域指向新节点
    return 1; // 插入成功
}

int insertTail(Node* head, ElementType e) { // 尾插法插入元素
    Node* newNode = (Node*)malloc(sizeof(Node)); // 分配新节点内存
    if (!newNode) { // 内存分配失败
        printf("内存分配失败，无法插入元素\n");
        return 0; // 插入失败
    }
    newNode->data = e; // 设置新节点数据域
    newNode->next = NULL; // 新节点指针域置空

    Node* p = head; // 指向头结点
    while (p->next) { // 遍历到链表末尾
        p = p->next;
    }
    p->next = newNode; // 尾节点指针域指向新节点
    return 1; // 插入成功
}

int inserMid(Node* head, int position, ElementType e) { // 在指定位置插入元素
    if (position < 1) { // 插入位置不合法
        printf("插入位置不合法\n");
        return 0; // 插入失败
    }
    Node* p = head; // 指向头结点
    for (int i = 1; i < position; i++) { // 遍历到插入位置的前一个节点（前驱）
        if (!p->next) { // 到达链表末尾，位置超出链表长度（链尾的指针域为NULL，!p->next即对NULL取反）
            break;
        }
        p = p->next; // 指向下一个节点
    }
    Node* newNode = (Node*)malloc(sizeof(Node)); // 分配新节点内存
    if (!newNode) { // 内存分配失败
        printf("内存分配失败，无法插入元素\n");
        return 0; // 插入失败
    }
    newNode->data = e; // 设置新节点数据域
    newNode->next = p->next; // 新节点指针域指向当前位置节点
    p->next = newNode; // 前一个节点指针域指向新节点
    return 1; // 插入成功
}

int deleteNode(Node* head, int position) { // 删除指定位置节点
    if (position < 1) { // 删除位置不合法
        printf("删除位置不合法\n");
        return 0; // 删除失败
    }
    Node* p = head; // 指向头结点
    for (int i = 1; i < position; i++) { // 遍历到删除位置的前一个节点
        if (!p->next) { // 到达链表末尾，位置超出链表长度
            printf("删除位置超出链表长度\n");
            return 0; // 删除失败
        }
        p = p->next;
    }
    Node* toDelete = p->next; // 指向要删除的节点
    if (!toDelete) { // 要删除的节点不存在
        printf("要删除的节点不存在\n");
        return 0; // 删除失败
    }
    p->next = toDelete->next; // 前一个节点指针域指向要删除节点的下一个节点
    free(toDelete); // 释放要删除节点内存
    return 1; // 删除成功
}

int freeList(Node* head) { // 释放链表内存
    Node* p = head; // 指向头结点
    while (p) { // 遍历链表
        Node* next = p->next; // 保存下一个节点指针
        free(p); // 释放当前节点内存
        p = next; // 指向下一个节点
    }
    return 1; // 释放成功
}

int main() {
    Node* list = InitList();
    inserHead(list, 1);
    inserHead(list, 2);
    inserHead(list, 3);
    Node* p = list->next; // 指向第一个节点
    while (p) {
        printf("%d ", p->data);
        p = p->next;
    }   
    printf("\n");
    freeList(list);
    return 0;
}